package com.lwt.codetop.linkedLists;

// 142. 环形链表||

/**
 * 环形链表1：链表判断是否存在环
 * 环形链表||：找到环的入口
 * 思路：背过，快慢指针
 *           一开始快2，慢1，相遇后快回到起点，然后快慢一起1步走，再次相遇即为环的入口
 */
public class LinkedListCycleII {
    public static void main(String[] args) {
        //构建测试用例 创建有环链表
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        // 制造环，让 node4 的 next 指向 node2
        head.next.next.next.next = head.next;

        // 找到环的入口
        ListNode res = detectCycle(head);
        System.out.println(res.val);
    }

    /**
     * 找到环的入口
     * @param head
     * @return
     */
    private static ListNode detectCycle(ListNode head) {
        if(head == null) return head;
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                fast = head;
                while (fast != slow){
                    fast =fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }


}
